package 蓝桥杯算法;

import java.util.Arrays;

public class day05 {
    public static void main(String[] args) {
       day05 a=new day05();
       String s="asd";
       String t="dsa";
        System.out.println( a.isAnagram(s,t));

    }
    static class Node{//创建链表
        int value;
        Node next;
        public Node(int value){
            this.next=next;
            this.value=value;
        }
    }
    static class LinkedList { //创建链表
        int size;
        Node head;

        public LinkedList() {
            this.size = 0;
            this.head = new Node(0);
        }

        public void addNode(int value) {
            Node newNode = new Node(value);
            if (head == null) {
                head = newNode;
            } else {
                Node current = head;
                while (current.next != null) {
                    current = current.next;
                }
                current.next = newNode;
            }
        }
    }
    public Node removeNode(int index,Node head) {
        Node dummyHead = new Node(0);//虚拟头节点
        dummyHead.next = head;
        Node fast = dummyHead;
        Node slow = dummyHead;
        for(int i=0;i<index;i++){
            fast=fast.next;
        }
        while(fast!=null){//最后一次遍历完是null
            fast=fast.next;
            slow=slow.next;//结束后结果是前一个结点
        }
        if(slow.next!=null) {
            slow.next = slow.next.next;
        }
        return dummyHead.next;//真正的头节点
    }
    public Node getintersectionNode(Node head1,Node head2){
        Node curA=head1;
        Node curB=head2;
        int lenA=0;int lenB=0;
        while(curA!=null){
            lenA++;
            curA=curA.next;
        }
        while (curB!=null){
            lenB++;
            curB=curB.next;
        }
        curB=head2;
        curA=head1;
        if(lenA>lenB){
            int temp=lenA-lenB;
            for(int i=0;i<temp;i++){
                curA=curA.next;
            }
        }
        else{
            int temp=lenB-lenA;
            for(int i=0;i<temp;i++){
                curB=curB.next;
            }
        }
        while(curA!=null){
            if(curA==curB){
                return curA;
            }
            curB=curB.next;
            curA=curA.next;
        }
        return null;
    }
    //有效字母异位词
    //区分大小写
    public boolean isAnagram(String s,String t){
        char[] schar=s.toCharArray();
        char[] tchar=t.toCharArray();
        Arrays.sort(schar);
        Arrays.sort(tchar);
       return Arrays.equals(schar,tchar);
    }
    //不区分大小写
    public boolean isAnagram1(String s,String t){//哈希法
        int[] record=new int[52];
        for(int i=0;i<s.length();i++){
            record[s.charAt(i)-'a']++;//转化成字母
        }
        for(int i=0;i<t.length();i++) {
            record[t.charAt(i)-'a']--;
        }
        for(int count:record){
            if(count!=0){
                return false;
            }
        }
        return true;
    }
    public boolean isAnagram2(String s,String t){
        if(s.length()!=t.length()){
            return false;
        }
        char[] record1=s.toCharArray();
        char[] record2=t.toCharArray();
        for(int i=0;i<record1.length;i++){
            for(int j=0;j<record2.length;j++){
                if(record1[i]==record2[j]){
                    record2[j]=0;
                    break;
                }else {
                    return false;
                }
            }
        }
        return true;
    }

}

